package chapter11;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * @author lzy
 * @version v1.0
 * Create DateTime: 2019/2/19 18:55
 */
public class Median<E> {
    private PriorityQueue<E> minP; //最小堆
    private PriorityQueue<E> maxP; //最大堆
    private E m; //当前中值

    public Median() {
        this.minP = new PriorityQueue<>();
        this.maxP = new PriorityQueue<>(Collections.reverseOrder());
    }

    public static void main(String[] args) {
        Median<Integer> median = new Median<>();
        median.addAll(Arrays.asList(34, 90, 67, 45, 1, 4, 5, 6, 7, 9, 10));
        System.out.println("中值为：" + median.getM());
    }

    private int compare(E e, E m) {
        Comparable<? super E> cmpr = (Comparable<? super E>) e;
        return cmpr.compareTo(m);
    }

    public void add(E e) {
        // 第一个元素
        if (m == null) {
            m = e;
            return;
        }
        // 小于中值，加入最大堆
        if (compare(e, m) <= 0) {
            maxP.add(e);
        } else {
            minP.add(e);
        }

        // 判断两个堆之间容量差距是否大于等于2，如果是需要调整当前中值
        if (minP.size() - maxP.size() >= 2) {
            //最小堆的元素个数多，说明大于中值的元素多
            //将m加入最大堆中，并将最小堆的根移除后赋给中值
            maxP.add(m);
            this.m = minP.poll();
        } else if (maxP.size() - minP.size() >= 2) {
            //最大堆的元素个数多，说明小于中值的元素多
            minP.add(m);
            this.m = maxP.poll();
        }
    }

    public void addAll(Collection<? extends E> c) {
        for (E e : c) {
            add(e);
        }
    }

    public E getM() {
        return this.m;
    }
}
